package a05_双指针法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * a09_三数之和复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/1/2
 */
public class a09_三数之和复习3 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        Arrays.sort(nums);
        outer:for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0){
                break outer;
            }
            if(i > 0 && nums[i] == nums[i-1]){
                continue outer;
            }

            int j = i + 1;
            int k = nums.length - 1;
            inner:while (j < k) {
                if(j > (i+1) && nums[j] == nums[j-1]){
                    j++;
                    continue inner;
                }
                if(k < (nums.length - 1) && nums[k] == nums[k+1]){
                    k--;
                    continue inner;
                }
                if(nums[i] + nums[j] + nums[k] > 0){
                    k--;
                }else if(nums[i] + nums[j] + nums[k] < 0){
                    j++;
                }else {
                    List<Integer> result = new ArrayList<>();
                    result.add(nums[i]);
                    result.add(nums[j]);
                    result.add(nums[k]);
                    resultList.add(result);
                    j++;
                    k--;
                }

            }
        }
        return resultList;
    }
}
